package Leetcode;

import base.ListNode;

/**
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 * L0 → L1 → … → Ln - 1 → Ln
 * 请将其重新排列后变为：
 * L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
 * 输入：head = [1,2,3,4,5]
 * 输出：[1,5,2,4,3]
 */
public class 力扣143_重排链表 {
    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        a.next = b;
        b.next = c;
        c.next = d;
        d.next = e;

        ListNode listNode = reorderList(a);
        System.out.println(listNode);
    }

    // 寻找链表中点 + 链表逆序 + 合并链表
    static ListNode reorderList(ListNode head) {
        ListNode aList = head;
        ListNode bList = null;

        // 链表总长度
        int length = 0;
        while (aList != null) {
            length++;
            aList = aList.next;
        }

        // 从中间拆分两个链表
        aList = head;
        int halfLength = (length + 1) / 2;
        for (int i = 1; aList != null; i++) {
            if (i == halfLength) {
                bList = aList.next;
                aList.next = null;
                break;
            }
            aList = aList.next;
        }

        // 将第二个链表反转
        ListNode bListPre = null;
        ListNode bListTemp = bList;
        while (bListTemp != null) {
            ListNode next = bListTemp.next;
            bListTemp.next = bListPre;
            bListPre = bListTemp;
            bListTemp = next;
        }
        bList = bListPre;

        // 合并两个链表 观察得到 奇数个数据 链表a > 链表b  偶数个数据 链表a = 链表b
        // 依次将第二个链表插入第一个链表的后边
        aList = head;
        while (aList != null && bList != null) {
            ListNode aNext = aList.next;
            ListNode bNext = bList.next;
            aList.next = bList;
            bList.next = aNext;
            aList = aNext;
            bList = bNext;
        }
        return head;
    }

    // 审题错误 得出的代码 为按照奇偶顺序排列
//    static ListNode reorderList(ListNode head) {
//        ListNode aList = head;
//        ListNode bList = null;
//        // 将原来列表拆分为两个列表  在第一个列表的基础上 每次抽取下一个节点到第二个链表
//        while (aList != null && aList.next != null) {
//            // 处理第一个链表 将next移除
//            ListNode next = aList.next;
//            aList.next = next.next;
//            aList = next.next;
//            // 处理第二个链表 将移除的next放到链表头部
//            next.next = bList;
//            bList = next;
//        }
//        // 合并两个链表 观察得到 奇数个数据 链表a > 链表b  偶数个数据 链表a = 链表b
//        // 依次将第二个链表插入第一个链表的后边
//        aList = head;
//        while (aList != null && bList != null) {
//            ListNode aNext = aList.next;
//            ListNode bNext = bList.next;
//            aList.next = bList;
//            bList.next = aNext;
//            aList = aNext;
//            bList = bNext;
//        }
//        return head;
//    }

}
